As data storage densities and data transmission rates increase, the ability of hardware devices to correctly recognize binary data diminishes. Many communications systems perform forward error correction (FEC) to improve data transmission accuracy and to ensure data integrity. FEC helps reduce bit error rates (BER) in applications such as data storage, digital video broadcasts, and wireless communications.
Convolutional coding and block coding are two forms of FEC. Block coding typically adds redundant bits to a message. For example, parity bits are added to ensure an even sum. If an odd sum is received, an error is detected. In convolutional coding, a transmitted stream is generated from an input stream. A Viterbi decoder is used to decode the received stream to identify a most probable transmitted stream, which is used to recover the input stream.
Referring now to FIG. 1, a first device 10-1 communicates with a second device 10-2 over a communications channel 12. As can be appreciated, the devices 10-1 and 10-2 are simplified for discussion purposes. Additional signal processing is typically performed before and/or after the convolutional encoding and/or Viterbi decoding.
The communications channel can be hardwired or wireless. For example, the communications channel 12 can be an Ethernet network, a wireless local area network, a bus for a hard drive, etc. The first device 10-1 includes components 14-1 that provide an input stream to a convolutional encoder 16-1 and that receive a decoded stream from a Viterbi decoder 18-1. Likewise, the device 10-2 includes components 14-2 that provide an input stream to a convolutional encoder 16-2 and that receive a decoded stream from a Viterbi decoder 18-2. The components 14-1 of the first device 10-1 may be similar to and/or different than the components 14-2 of the second device 10-2. The convolutional encoders 16 transform the input stream into a transmitted stream before the data is output onto the communications channel 12. The Viterbi decoders 18 decode the received stream to recover a most probable transmitted stream.
For example, a rate ½ convolutional code transmits 2 output bits for each input bit. Referring now to FIG. 2, a trellis 20 is typically used to generate the rate ½ convolutional code. The trellis 20 includes four states (00, 01, 10 and 11). At each point, the trellis 20 splits into two paths. An upper path represents a 0 input and a lower path represent a 1 input. An initial state of 00 is presumed. Using the trellis 20 in FIG. 2, an input stream of 1101 generates an output of 11101101. In other words, the MSB of the input stream (1) corresponds to 11 in the transmitted stream. The 2nd MSB of the input stream (1) corresponds to 10 in the transmitted stream. The 3rd MSB of the input stream (0) corresponds to 11 in the transmitted stream. The LSB of the input stream (1) corresponds to 01 in the transmitted stream.
A received stream must be decoded. Some decoders use a Viterbi algorithm to decode the received stream. The Viterbi algorithm compares the received stream to all possible transmitted streams and selects the transmitted stream that is closest to the received stream. The transmitted stream that is selected by the Viterbi algorithm has a minimum number of bits that are different from the received stream—or a minimum bit distance. Once the most probable transmitted stream is identified, the input stream is generated from the selected trellis path.
Referring now to FIG. 3, to decode an input sequence of 10101010, a trellis 24 is used. The distance between each pair of received bits and the corresponding bits in the trellis 24 (or possible transmitted bits) are identified. For example, the 1 on the path AB results from the comparison of the received bits 10 to the bits 00 on the AB path. The received bits 10 differ from the trellis bits 00 for AB by one bit position.
If there are two paths that end at the same point or state, the Viterbi decoder selects the path with the minimum bit distance. If the two paths have the same distance, either path can be selected. In other words, the probability of decoding is the same for each path. In this particular example, the path through ACGJL in the trellis 24 has a bit distance of 2. The path ACGJL is generated by an input of 1100. The input of 1100 into the trellis 20 in FIG. 2 would correspond to an output of 11101110, which also has a bit distance of 2 from the received word. While a rate-½ convolutional code was shown, other rate convolutional codes may be used by Viterbi decoders.
Some conventional Viterbi decoders provide both a full decision output and an early decision output. The early decision output may be used by one or more control loops such as baseline loops, timing loops, gain loops and finite impulse response (FIR) adaptation loops. The early decision output may be used by the control loops to generate error signals. If the early decision output is incorrect, these control loops will cause errors. Therefore, the Viterbi decoder should not output the early decision output to these control loops when the early decision output is incorrect.
For example, for magnetic recording equalization targets containing a (1+D) factor, quasi-catastrophic sequences correspond to runs of alternating 1's and 0's that exceed a path memory depth of the Viterbi decoder that is matched to the equalization target. For equalization targets with a (1+D) factor, bit sequences with long transition runs can cause problems with the early decision output. For example, a sequence +−+−+−+−+−+−+−+−+−+−+−+− can be decoded to either +−+−+−−−−−+−+−+−+−+−+−+−+ or ++−+++++−+−+−+−+−+−+−+−. For an all positive target, e.g. 4+6D+3D2+2D3+1 D4, an output of a reconstruction filter can be either ?,?,?,0,0,0,−8,−12,−14,−16,−8,−4,−2,0,0,0,0,0 or ?,?,?,0,0,8,12,14,16,8,4,2,0,0,0,0,0 instead of ?,?,?,0,0,0,0,0,0,0,0,0,0,0,0,0,0. This incorrect early decision output would adversely impact the performance of the control loops that use the early decision output.
The Viterbi decoder makes the early decision errors when there is a tie between two different paths that have the same path metric value or bit distance. The tie is broken by deterministically selecting one best path over the other based on the current state of the path. A path is denoted as follows:(uF, uF−1, . . . , uE, uE−1, . . . , u1, u0);mwhere index F denotes the full decision depth. Index E denotes the early decision depth. Each variable uiε(−1,1) denotes a bit in the Viterbi path memory and m is the path metric value for the path. The current state of the path for a 16 state trellis is given by bits u0, u1, u2, u3.
For example, using equalization target H(D)=(1+D)G(D), there is a tie in the path metric between the two best paths PA and PB at time i:PA,i=(?, ?, . . . , ?,+1,−1,+1,−1,+1,−1,+1,−1,+1,−1,+1,−1,+1,−1,+1,−1,+1,−1,+1);m PB,i=(?, ?, . . . , ?,−1,+1,−1,+1,−1,+1,−1,+1,−1,+1,−1,+1,−1,+1,−1,+1,−1,+1,−1);m The underscored bits represent the early decision output for respective paths PA and PB. If the Viterbi decoder at time i selects path PA as the winner, then the early decision output is xi=1.
For time i+1, the winning branch for path PA corresponds to −1 and the winning branch for path PB corresponds to +1. At time t=i+1, the paths PA and PB are as follows:PA,i+1=(?, ?, . . . , ?,+1,−1,+1,−1,+1,−1,+1,−1,+1,−1,+1,−1,+1,−1,+1,−1,+1,−1,+1,−1);m PB,i+1=(?, ?, . . . , ?,−1,+1,−1,+1,−1,+1,−1,+1,−1,+1,−1,+1,−1,+1,−1,+1,−1,+1,−1,+1);m 
Since the two paths PA and PB were tied at time i and the branch metrics for each path are equal, the paths PA and PB will be tied at time i+1 as well. At time i, the leading state for path PA was (+1,−1,+1,−1) and the leading state for path for path PB was (−1,+1,−1,+1). At time i+1, however, the leading state for path PA is (−1,+1,−1,+1) and the leading state for path PB is (+1,−1,+1,−1).
Since the Viterbi decoder selected the path with leading state (+1,−1,+1,−1) when there was a tie between the two at time i, the Viterbi decoder will do the same at time t=i+1. Therefore, the path PB will be the winner at time i+1 and the early decision output will be xi+1=1. If this continues for a few cycles, the output sequence would be +1,+1,+1,+1,+1 for this segment. However, the correct output sequence should be +1,−1,+1,−1,+1.